#ifndef N_Q_P_
#define N_Q_P_
#include <cstdlib>
#include <string>
#include <vector>

namespace
{
inline bool check(const std::vector<int>& path, int i, int j)
{
    for (int k = 0; k < i; k++) {
        if (j == path[k] || std::abs(i - k) == std::abs(j - path[k])) return false;
    }
    return true;
}

inline int common(std::vector<std::vector<std::string>>& all_plan,
                  std::vector<int>                       path,
                  int                                    i,
                  int                                    n)
{
    if (i == n) {
        std::vector<std::string> one_plan(n);
        std::string              plan(n, 'O');
        for (int k = 0; k < path.size(); k++) {
            plan[path[k]] = 'X';
            one_plan[k]   = plan;
            plan[path[k]] = 'O';
        }
        all_plan.push_back(one_plan);
        return 1;
    }
    int ans = 0;
    for (int pos = 0; pos < n; pos++) {
        if (check(path, i, pos)) {
            path[i] = pos;
            ans += common(all_plan, path, i + 1, n);
        }
    }
    return ans;
}

inline int common2(int limit, int col, int left, int right)
{
    if (col == limit) return 1;

    int ban       = col | left | right;
    int candidate = limit & (~ban);
    int place     = 0;
    int ans       = 0;
    while (candidate != 0) {
        place = candidate & (-candidate);
        candidate ^= place;
        ans += common2(limit, (col | place), (left | place) >> 1, (right | place) << 1);
    }
    return ans;
}
}   // namespace

namespace lxj
{
// 力扣.51 普通递归版本，o(n!)复杂度
inline std::vector<std::vector<std::string>> solveNQueens(int n)
{
    std::vector<std::vector<std::string>> all_plan;
    std::vector<int>                      path(n);
    int                                   cnt = common(all_plan, path, 0, n);
    return all_plan;
}

// 力扣52. N 皇后 II (位运算版本)
inline int totalNQueens(int n)
{
    if (n < 1) return 0;

    int limit = (1 << n) - 1;
    return common2(limit, 0, 0, 0);
}
}   // namespace lxj

#endif